package com.future;

import java.util.*;

/**
 * Description: 239. 滑动窗口最大值 （算法体系班：Code01_SlidingWindowMaxArray）
 *
 * @author weiruibai.vendor
 * Date: 2022/6/11 16:46
 */
public class Solution_239 {

    public static void main(String[] args) {
        int[] nums = new int[]{1, 3, -1, -3, 5, 3, 6, 7};
        int k = 3;
        nums = new int[]{7, 2, 4};
        k = 2;
        nums = new int[]{1, 3, 1, 2, 0, 5};
        k = 3;
        System.out.println(maxSlidingWindow(nums, k));
    }


    public static int[] maxSlidingWindow(int[] arr, int w) {
        if (arr == null || w < 1 || arr.length < w) {
            return null;
        }
        // qmax 窗口最大值的更新结构
        // 放下标
        LinkedList<Integer> qmax = new LinkedList<Integer>();
        int[] res = new int[arr.length - w + 1];
        int index = 0;
        for (int R = 0; R < arr.length; R++) {
            while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[R]) {
                qmax.pollLast();
            }
            qmax.addLast(R);
            if (qmax.peekFirst() == R - w) {
                /**
                 * 重点，说明该下标已经过期了，需要移除(这就是qmax存的是下标的原因)
                 */
                qmax.pollFirst();
            }
            if (R >= w - 1) {
                /**
                 * 说明窗口已经形成，开始收集当前窗口最大值
                 */
                res[index++] = arr[qmax.peekFirst()];
            }
        }
        return res;
    }

}
